package _06_动态规划;

/**
 *
 */
public class _剑指Offer47_礼物的最大价值 {

    // 满足最优子结构性质，和无后效性质，可以使用动态规划求解
    public int maxValue(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        // 定义dp数组, 前i，j元素的礼物最大价值
        int[][] dp = new int[rows][cols];
        // 设置初始值
        dp[0][0] = grid[0][0];
        for (int row = 1; row < rows; row++) {
            dp[row][0] = dp[row - 1][0] + grid[row][0];
        }
        for (int col = 1; col < cols; col++) {
            dp[0][col] = dp[0][col - 1] + grid[0][col];
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j -1]) + grid[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }

}
